/*
给定一个 24 小时制（小时:分钟 "HH:MM"）的时间列表，找出列表中任意两个时间的最小时间差并以分钟数表示。

 

示例 1：

输入：timePoints = ["23:59","00:00"]
输出：1
示例 2：

输入：timePoints = ["00:00","23:59","00:00"]
输出：0
 

提示：

2 <= timePoints <= 2 * 104
timePoints[i] 格式为 "HH:MM"

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/minimum-time-difference
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/

#include "../stdc++.h"

// 排序
class Solution {
private:
    int getMinutes(const string& time) {
        int hour = std::stoi(time.substr(0, 2));
        int minute = std::stoi(time.substr(3, 2));
        return hour * 60 + minute;
    }
public:
    int findMinDifference(vector<string>& timePoints) {
        sort(timePoints.begin(), timePoints.end());
        int res{24 * 60};
        int n = timePoints.size();
        int t0Minutes = getMinutes(timePoints[0]);
        int preMinutes = t0Minutes;
        for (int i{1}; i < n; ++i) {
            int minutes = getMinutes(timePoints[i]);
            res = min(res, minutes - preMinutes);
            preMinutes = minutes;
        }
        res = min(res, t0Minutes + 1440 - preMinutes);
        return res;
    }
};

// 鸽巢原理
// 一共有 24 * 60=1440 种不同的时间。由鸽巢原理可知，如果 timePoints 的长度超过 1440，那么必然会有两个相同的时间，此时可以直接返回 0。
class Solution {
private:
    int getMinutes(const string& time) {
        int hour = std::stoi(time.substr(0, 2));
        int minute = std::stoi(time.substr(3, 2));
        return hour * 60 + minute;
    }
public:
    int findMinDifference(vector<string>& timePoints) {
        int n = timePoints.size();
        if (n > 1440) {
            return 0;
        }
        sort(timePoints.begin(), timePoints.end());
        int res{24 * 60};
        int t0Minutes = getMinutes(timePoints[0]);
        int preMinutes = t0Minutes;
        for (int i{1}; i < n; ++i) {
            int minutes = getMinutes(timePoints[i]);
            res = min(res, minutes - preMinutes);
            preMinutes = minutes;
        }
        res = min(res, t0Minutes + 1440 - preMinutes);
        return res;
    }
};
